/*	Interactive Gravitational Simulator
	Project: IGS Core
	File: KDTree.cpp
	Author: Mike Bantegui <mbante2@gmail.com>, Hofstra University 
	Copyright (C) 2012 - 2013 Mike Bantegui

	This file is part of the IGS software package for simulating
	the N-Body problem in real-time. This was developed as part
	of a departmental honors thesis project at Hofstra University
	in the Spring 2012 semester.

	IGS is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	IGS is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

#include "Body.h"
#include "KDTree.h"
#include "Node.h"
#include <algorithm>
#include <omp.h>

namespace IGS
{

// Constructs an empty KDTree with the specified opening
KDTree::KDTree(const double theta) : Tree(theta, KDTree::LeafSize)
{
}

// Constructs an empty KDTree with the specified opening and leaf size
KDTree::KDTree(const double theta, const unsigned leafSize) : Tree(theta, KDTree::BranchSize, leafSize)
{
}

// Destructs the KDTree
KDTree::~KDTree()
{
}

// Returns the name of the KDTree
std::string KDTree::Name() const
{
	return "kdtree";
}

#ifdef PoolAllocator
// Calculates the amount of nodes required for a system of N Bodies
unsigned KDTree::CalculatePoolSize(const int N) const
{
#ifdef BalancedKDTree
	// Because the tree is perfectly balanced, we can guarantee that
	// we will only ever need N nodes to be allocated. The factor of
	// 2 is a safety factor and will be unlikely to be neccessary.
	return 2 * N;
#else
	// We use a reserve safety factor of 10 over the balanced case
	// to handle pathologic cases such as when the tree is highly
	// unbalanced.
	return 20 * N;
#endif
}
#endif

// Branches the KDTree at the given node, inserting all the bodies
// as children of the node.
Node *KDTree::Branch(std::vector<Body *> bodies, const Vector &min,
	const Vector &max, const unsigned depth)
{
	// Create empty leaf node
	if (bodies.empty())
		return NULL;
	
	// Create leaf node
	if (bodies.size() <= LeafSize)
		return AllocateNode(bodies);

	const size_t n = bodies.size() / BranchSize;
	std::vector<Body *> Left, Right;
	Left.reserve(n); Right.reserve(n);
	
	const unsigned k = depth % 3;

#ifdef BalancedKDTree
	std::sort(bodies.begin(), bodies.end(),
		[k] (Body *a, Body *b) { return a->Position[k] < b->Position[k]; });
	const double mid = bodies[n]->Position[k];
#else
	const double mid = (min[k] + max[k]) / 2;
#endif

	Vector leftMax = max; leftMax[k] = mid;
	Vector rightMin = min; rightMin[k] = mid;

	// Collect bodies into each of the volumes
	for (size_t i = 0; i < bodies.size(); i++)
	{
		Body *b = bodies[i];
		if (b->Position[k] < mid) Left.push_back(b); // Left
		else Right.push_back(b); // Right
	}

	// Free memory being used
	bodies.clear(); bodies.shrink_to_fit();
	std::vector<Node *> branches(KDTree::BranchSize, NULL);

	// Recursively branch and insert the bodies into the half planes
	#pragma omp parallel sections
	{
		#pragma omp section
		branches[0] = Branch(Left, min, leftMax, depth + 1);
		#pragma omp section
		branches[1] = Branch(Right, rightMin, max, depth + 1);
	}

	return AllocateNode(branches);
}

}